//***********************************折半插入排序***************************************
// 2. 折半查找插入位置： 二分插入排序
// 目标元素在前半子序列中查找时，采用二分查找法
// length较大时，折半的效率比直接好，平均性能优于直接插入排序
// 时间复杂度O(n²)，空间复杂度O(1)
function insertSort_half(arr) {
  for(let i = 1; i <= arr.length-1; i++) {
    let temp = arr[i];
    // 左右两个端点的下标值
    let low = 0;
    let high = i-1;
    //二分查找，快速逼近
    while(low < high) {
      //整除
      let mid = Math.floor((low + high) / 2);
      if(temp >= arr[mid]) {
        low = mid + 1;
      } else {
        high = mid -1;
      }
    }
    //结束后，插入下标位置为high+1
    //依次后移
    for(let j=i-1; j >= high; j--) {
      arr[j+1] = arr[j];
    }
    arr[high + 1] = temp;
  }
}

//测试用例
let arr = [96,29,54,23,83,16,32,7,10,3,5,23]
insertSort_half(arr);
console.log(arr);
